package leetcode.dp;

import java.util.Arrays;

public class CountAllPossibleRoutes1575 {
    public static void main(String[] args) {

    }


    class Solution1 {

        int mod = 1000000007;
        int[][] cache;


        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            int n = locations.length;
            cache = new int[n][fuel + 1];
            for (int i = 0; i < n; i++) {
                Arrays.fill(cache[i], -1);
            }
            return dfs(locations, start, finish, fuel);
        }
        public int dfs(int[] locations, int start, int end, int fuel) {
            int n = locations.length;
            if (cache[start][fuel] != - 1) {
                return cache[start][fuel];
            }
            if (fuel == 0 && start != end) {
                cache[start][fuel] = 0;
                return cache[start][fuel];
            }
            boolean hasNext = false;
            for (int i = 0; i < n; i++) {
                if (i != start) {
                    int need = Math.abs(locations[i] - locations[start]);
                    if (need <= fuel) {
                        hasNext = true;
                        break;
                    }
                }
            }
            if (fuel != 0 && !hasNext) {
                cache[start][fuel] = start == end ? 1 : 0;
                return  cache[start][fuel];
            }
            int sum = start == end ? 1 : 0;
            for (int i = 0; i < n; i++) {
                if (i != start) {
                    int need = Math.abs(locations[i] - locations[start]);
                    if (need <= fuel) {
                        sum += dfs(locations, i, end, fuel - need);
                        sum %= mod;
                    }
                }
            }
            cache[start][fuel] = sum;
            return cache[start][fuel];
        }
    }

    class Solution2 {

        int mod = 1000000007;
        int[][] cache;

        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            int n = locations.length;
            cache = new int[n][fuel + 1];
            for (int i = 0; i < n; i++) {
                Arrays.fill(cache[i], -1);
            }
            return dfs(locations, start, finish, fuel);
        }
        public int dfs(int[] locations, int start, int finish, int fuel) {
            if (cache[start][fuel] != - 1) {
                return cache[start][fuel];
            }
            int need = Math.abs(locations[start] - locations[finish]);
            if (need > fuel) {
                cache[start][fuel] = 0;
                return cache[start][fuel];
            }
            int n = locations.length;
            int sum = start == finish ? 1 : 0;
            for (int i = 0; i < n; i++) {
                if (i != start) {
                    need = Math.abs(locations[start] - locations[i]);
                    if (need <= fuel) {
                        sum += dfs(locations, i, finish, fuel - need);
                        sum %= mod;
                    }
                }
            }
            cache[start][fuel] = sum;
            return sum;
        }
    }

    class Solution3 {
        int mod = 1000000007;

        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            int n = locations.length;
            int[][] dp = new int[n][fuel + 1];
            for (int i = 0; i <= fuel; i++) {
                dp[finish][i] = 1;
            }
            for (int i = 0; i <= fuel; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        if (j != k) {
                            int need = Math.abs(locations[j] - locations[k]);
                            if (i >= need) {
                                dp[j][i] += dp[k][i - need];
                                dp[j][i] %= mod;
                            }
                        }
                    }
                }
            }
            return dp[start][fuel];
        }
    }

    class Solution4 {

        int mod = 1000000007;

        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            int n = locations.length;
            int[][] dp = new int[n][fuel + 1];
            for (int i = 0; i <= fuel; i++) {
                dp[finish][i] = 1;
            }
            for (int i = 0; i <= fuel; i++) {
                for (int j = 0; j < n; j++) {
                    int need = Math.abs(locations[j] - locations[finish]);
                    if (need > i) {
                        System.out.println(j);
                        System.out.println(finish);
                        dp[j][fuel] = 0;
                    } else {
                        for (int k = 0; k < n; k++) {
                            if (k != j) {
                                need = Math.abs(locations[j] - locations[k]);
                                if (need <= i) {
                                    dp[j][i] += dp[k][i - need];
                                    dp[j][i] %= mod;
                                }
                            }
                        }
                    }
                }
            }
            return dp[start][fuel];
        }
    }

    //Todo: 不懂
    class Solution5 {
        static final int MOD = 1000000007;

        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            int n = locations.length;
            int startPos = locations[start];
            int finishPos = locations[finish];
            Arrays.sort(locations);
            for (int i = 0; i < n; ++i) {
                if (startPos == locations[i]) {
                    start = i;
                }
                if (finishPos == locations[i]) {
                    finish = i;
                }
            }

            int[][] dpL = new int[n][fuel + 1];
            int[][] dpR = new int[n][fuel + 1];
            dpL[start][0] = dpR[start][0] = 1;

            for (int used = 0; used <= fuel; ++used) {
                for (int city = n - 2; city >= 0; --city) {
                    int delta = locations[city + 1] - locations[city];
                    if (used >= delta) {
                        dpL[city][used] = ((used == delta ? 0 : dpL[city + 1][used - delta]) * 2 % MOD + dpR[city + 1][used - delta]) % MOD;
                    }
                }
                for (int city = 1; city < n; ++city) {
                    int delta = locations[city] - locations[city - 1];
                    if (used >= delta) {
                        dpR[city][used] = ((used == delta ? 0 : dpR[city - 1][used - delta]) * 2 % MOD + dpL[city - 1][used - delta]) % MOD;
                    }
                }
            }

            int ans = 0;
            for (int used = 0; used <= fuel; ++used) {
                ans += (dpL[finish][used] + dpR[finish][used]) % MOD;
                ans %= MOD;
            }
            if (start == finish) {
                ans = (ans + MOD - 1) % MOD;
            }
            return ans;
        }
    }
}
